package com.atguigu.sort;

import java.util.Arrays;

/**
 * 基数排序
 *
 * 耗时
 * work: 0.008s
 * 千万: 0.42s
 * 亿级, 会直接栈溢出
 */
public class RedixSort {
    public static void main(String[] args) {
//        int[] arr={1000,11,34,567,1,9,10,333};
        int[] arr = ArrCreator.createRandArr(ArrCreator.testVelocitySize*100);
//        System.out.println(Arrays.toString(arr));
        ArrCreator.beforeSort();
        sort(arr);
        ArrCreator.afterSort();
//        System.out.println(Arrays.toString(arr));

    }

    public static int BUCKET_COUNT=10;

    public static void sort(int[] arr){
        if (arr.length==0) {
            return;
        }
        // 1. 准备工作. 排序桶与容量桶
        int[][] bucketArr=new int[BUCKET_COUNT][arr.length];
        int[] eachBucketCountArr=new int[BUCKET_COUNT];

        int max=arr[0];
        for (int eachNum : arr) {
            if (eachNum>max) {
                max=eachNum;
            }
        }
        int maxLength=(""+max).length();

        // 2. 逐次排序
        int tempBucketIndex;
        int tempEachBucketCount;
        int tempTotalCount;
        int tempEachBit=1;
        for (int length = 0; length < maxLength; length++) {
            for (int eachNum : arr) {
                tempBucketIndex = eachNum / tempEachBit % 10;
                tempEachBucketCount = eachBucketCountArr[tempBucketIndex];
                bucketArr[tempBucketIndex][tempEachBucketCount++] = eachNum;
                eachBucketCountArr[tempBucketIndex] = tempEachBucketCount;
            }
            tempTotalCount=0;
            for (int bucketIndex = 0; bucketIndex < BUCKET_COUNT; bucketIndex++) {
                if (eachBucketCountArr[bucketIndex]>0) {
                    for (int eachBucketCountIndex = 0; eachBucketCountIndex < eachBucketCountArr[bucketIndex]; eachBucketCountIndex++) {
                        arr[tempTotalCount++]=bucketArr[bucketIndex][eachBucketCountIndex];
                    }
                    eachBucketCountArr[bucketIndex]=0;
                }

            }
            tempEachBit*=BUCKET_COUNT;
//            System.out.println("arr="+ Arrays.toString(arr));
        }



    }
}
